package com.wlj.utils.suanfa;

public class InOrderTest {
    public static String inOrder(String preString,String postString){

        if(preString.isEmpty()){
            return "";
        }
        if(preString.length()==1){
            return preString;
        }
        char rootValue=preString.charAt(0);
        int leftRootIndex=postString.indexOf(preString.substring(1, 2));
        if(leftRootIndex==postString.length()-2){//缺少左子树或右子树

            return "("+inOrder(preString.substring(1),postString.substring(0, postString.length()-1))+rootValue+","+
                    rootValue+inOrder(preString.substring(1),postString.substring(0, postString.length()-1))+")";

        }else{//存在左子树和右子树

            return inOrder(preString.substring(1, leftRootIndex+2),postString.substring(0, leftRootIndex+1))
                    +rootValue+inOrder(preString.substring(leftRootIndex+2),postString.substring(leftRootIndex+1, postString.length()-1));

        }


    }


    public static void main(String[] args){

        String preString= "ABDEG";  //前序遍历串
        String postString="DGEBA";  //后序遍历串
        System.out.println(inOrder(preString,postString));

    }

}
